#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
#include <map>
#include <vector>

int table[255];
int numbers[] = {57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137, 147, 156, 163, 186 };
std::string peptide_str = "GASPVTCINDKEMHFRYW";

std::map<int, int> spectr;

int str2int(std::string str)
{
	int result = 0;
	for (auto it=str.begin(); it!=str.end(); it++)
	{
		char ch = *it;
		result += table[ch];
	}
	return result;
}

std::map<int,int> getCyclopeptide(std::string input)
{
	int size = input.size();
	std::map<int,int> peptide;
	std::reverse(input.begin(), input.end());
	std::string dbl_str = input+input;
	for (int i=1; i<size; i++)
	{
		for (int j=0; j<size; j++)
		{
			std::string cur = dbl_str.substr(j, i);
			int current = str2int(cur);
            auto f = peptide.find(current);
            if (f == peptide.end())
                peptide.insert(std::pair<int,int>(current, 1));
            else
                f->second = f->second + 1;
		}
	}
    peptide.insert(std::pair<int,int>(0,1));
    peptide.insert(std::pair<int,int>(str2int(input),1));
	return peptide;
}

int score(std::map<int,int> peptide)
{
    int score = 0;
    int p;
    for (auto it=spectr.begin(); it!=spectr.end(); it++)
    {
        if (it->first == 0)
            continue;
        auto f = peptide.find(it->first);
        if (f != peptide.end())
        {
            if (it->second > f->second)
            {
                score += f->second;
            } else
                score += it->second;
        }
    }
    return score;
}

void expand(std::list<std::pair<std::string, int>>* from, std::list<std::pair<std::string, int>>* to)
{
	for (auto it=from->begin(); it!=from->end(); it++)
	{
        std::string cur = it->first;
		for (auto ch=peptide_str.begin(); ch!=peptide_str.end(); ch++)
		{
            std::string temp = cur + *ch;
			to->push_back(std::pair<std::string,int>(temp, score(getCyclopeptide(temp))));
		}
	}
}

int mass(std::map<int,int> peptide)
{
    return peptide.rbegin()->first;
}

bool score_compare(std::pair<std::string, int> a, std::pair<std::string, int> b)
{
    return a.second > b.second;
}

bool length_compare(std::pair<std::string, int> a, std::pair<std::string, int> b)
{
    return a.first.length() < b.first.length();
}

void cut(std::list<std::pair<std::string, int>>* from, std::list<std::pair<std::string, int>>* to, int N)
{
    if (from->size() > N)
        from->sort(score_compare);
    auto end = from->begin();
    for (int i=0; i<std::min(N, (int) from->size()); i++)
        end++;
    to->assign(from->begin(), end);
}

int main()
{
	FILE* file = fopen("stepic_dataset.txt", "r");
	FILE* table_file = fopen("integer_mass_table.txt", "r");
	FILE* out = fopen("result.txt", "w");
	for (int i=0; i<20; i++)
	{
		char c[15];
		int num;
		fscanf(table_file, "%s %d", &c, &num);
		table[c[0]] = num;
	}
    int N;
    fscanf(file, "%d", &N);

	while (!feof(file))
	{
		int num;
		fscanf(file, "%d", &num);
		auto f = spectr.find(num);
		if (f == spectr.end())
			spectr.insert(std::pair<int,int>(num, 1));
		else
			f->second = f->second + 1;
	}
    int spectr_mass = mass(spectr);
    int max_score = 0;
    for (auto it=spectr.begin(); it!=spectr.end(); it++)
        max_score += it->second;

    int m = mass(getCyclopeptide("SCYINTSDSDIVERFWTRFYRYTN"));
    int s = score(getCyclopeptide("SCYINTSDSDIVERFWTRFYRYTN"));





	std::list<std::pair<std::string, int>>* cur = new std::list<std::pair<std::string, int>>();
	std::list<std::pair<std::string, int>>* prev = new std::list<std::pair<std::string, int>>();
    
    prev->push_back(std::pair<std::string, int>("",0));
    int leader_score = 0;
    std::list<std::string> leaders;

    while (!prev->empty())
    {
        expand(prev, cur);
        std::swap(cur, prev);
        cur->clear();
        for (auto it=prev->begin(); it!=prev->end(); it++)
        {
            std::map<int,int> peptide = getCyclopeptide(it->first);
            int peptide_mass = mass(peptide);
            
            if (peptide_mass > spectr_mass) 
                continue;
            if (peptide_mass == spectr_mass)
            {
                if (it->second == leader_score)
                {
                    leaders.push_back(it->first);
                }
                if (it->second > leader_score)
                {
                    leader_score = score(peptide);
                    leaders.clear();
                    leaders.push_back(it->first);
                }
            }
            cur->push_back(*it);
        }
        prev->clear();
        cut(cur, prev, N);
        cur->clear();
    }
    //leaders.sort(length_compare);
    for (auto it = leaders.begin(); it!=leaders.end(); it++)
    {
        std::string str = *it;
        fprintf(out, "%s\n", str.c_str());
	    for (int i=0; i<str.size()-1; i++)
	    {
		    fprintf(out,"%d-", table[str[i]]);
	    }
	    fprintf(out, "%d ", table[str[str.size()-1]]);
    }
	return 0;
}